\documentclass[12pt]{article}

\usepackage{traffic}
\usepackage[utf8]{inputenc}
\usepackage[pdftex]{graphicx}
\usepackage{epsfig}
     
\sloppy

\title{A multi-agent traffic control}

\author{Rafael Z. Godoy, Renato Malvezzi}


\address{Pontifícia Universidade Católica do Rio Grande do Sul}

\begin{document} 

\maketitle

\section{Introduction}
\label{Section:Introduction}
 
Our multi-agent implementation is a simulation of a traffic-control scenario of people walking on a 2-way street. There are some configurable parameters for the execution, but basically the simulation model should have at least a street intersection (a crossing), in which collisions can occur if two agents try crossing it at the same time. To avoid these collisions we developed a special kind of agent, a traffic coordinator. 

The following parameters are configurable before the environment creation:

\begin{itemize}
\item{Number of crossings, between 1 and 3. The number of traffic coordinators is directly proportional to this parameter.}
\item{The traffic intensity can be: low, medium or high. The total number of agents walking on the streets are defined by this parameter.}
\end{itemize}

The number of crossings and the traffic intensity defines the complexity of the simulated environment. A complex simulation has three crossings and a high traffic intensity, in which the collisions chances would be the biggest ones. 

%When the communication is enabled, the agents communicate and negotiate with each other to avoid these possible collisions. A simulation instance that not have communication between agents have an agent that is responsible to manage the crossings in order to avoid collisions. This traffic coordinator agent works similar to a semaphore.

%The Figure~\ref{fig:interface} shows a simulation for the system with low traffic intensity and one crossing. The agents %that represent people walking are represented on the user interface by an red circle. The green diamonds represent %obstacles, a part of the street in which people are not able to walk on.


%\begin{figure}[htb!]
%\centering\includegraphics[width=.55\textwidth]{interface.png}
%\caption
%        {\label{fig:interface} User interface prototype}
%\end{figure}

\section{Implementation}
\label{Section:Implementation}

Our implementation design is based on a common object-oriented design pattern called \textit{Model - View - Control}. First, on Section~\ref{Section:Implementation:Agents} we describe the two agents implemented for this simulation, then on Sections~\ref{Section:Implementation:Environment},~\ref{Section:Implementation:Model}, and~\ref{Section:Implementation:View} we describe the environment components. 

%The implementation consists of an environment that according to the the parameters selected as input of the simulation will instantiate a predefined view model of simulation. The environment is responsible for: adding and distributing the agents on their correspondent streets, according to the selected traffic intensity, and create the ground elements like squares that are part of the street and squares that are not, defined as obstacles.

%There are two kinds of agents: \emph{walker} and \emph{traffic coordinator}. The first one represent people that walks on the street. The goal of this agent is to walk on his defined way of the street, going back and forward on available squares of streets, the ones with no agents, indefinitely. When close to a crossing square, a square that is on two streets intersection, the agent will need to request to the traffic coordinator an authorization to proceed or, if the agents have the skill to communicate, negotiate with the agent from the other street which agent will pass. The \emph{traffic coordinator} works similar to a semaphore as it allows or cancels momentarily the traffic on each intersection. When a \emph{walker} is close to an street intersection, he will ask the \emph{traffic coordinator} to see if the street that he is walking is currently with the \emph{green light} to continue or not.

\subsection{Agents}
\label{Section:Implementation:Agents}

As mentioned before, there is two kinds of agents acting in the traffic-control environment: \textit{walker} and \textit{little blue}. The \textit{walker} agent walks into environment streets, and communicates with traffic coordinators (\textit{little blue}), asking for permission to cross intersections. Each \textit{walker} is associated to a unique street and keeps moving at the same street during the whole simulation. There is a traffic coordinator for each intersection in the grid. The \textit{little blue} agent controls which \textit{walker} agents will be able to cross his intersection at a given time. Below we describe each agent with more details.

\subsubsection{Walker}

\paragraph{Environment Perceptions\\\\}

The Figure~\ref{Figure:WalkerEnvPercepts} shows the \textit{walker} perceptions in which the source is the environment. On each execution step, all \textit{walker} agents add beliefs about their position in the grid, the direction from the street that they are into, and the position and content of each adjacent quadrant cell. A quadrant cell can have four types of content: A stop (a cell before an intersection), a walker, an obstacle or nothing (an empty cell).

\begin{figure}[h!]
\centering
\scalebox{0.5}{
	\epsfig{file=images/walker_env_percepts}}
\caption{Walker perceptions from the Environment.} 
\label{Figure:WalkerEnvPercepts}
\end{figure}

\paragraph{Communication with other agents\\\\}

There are two moments that a \textit{walker} might need to communicate with \textit{little blue}. The first moment is when a \textit{walker} does not know which \textit{little blue} agent is the traffic coordinator of the intersection that the \textit{walker} is about to cross. Then the \textit{walker} would send an \textit{askOne} message \texttt{responsable\underline{ }quad(NX,NY)} to all \textit{little blues}. The \textit{little blue} that owns that intersection will answer (asynchronously) to the \textit{walker} agent. The other moment that a \textit{walker} might send a message to \textit{little blue} is when his current position in the grid is a stop and he needs permission to cross the intersection. The \textit{walker} agent then send a \textit{tell} message \texttt{want\underline{ }cross(DX,DY,D)} to the \textit{little blue} agent that is the responsible for coordinates \textit{DX} and \textit{DY}. 

The Figure~\ref{Figure:AgentsCommunication} shows an sequence diagram of \textit{walker} and \textit{little blue} communication.

\begin{figure}[h!]
\centering
\scalebox{0.5}{
	\epsfig{file=images/agents_communication}}
\caption{Communication sequence diagram between \textit{walker} and \textit{little blue} agents.} 
\label{Figure:AgentsCommunication}
\end{figure}

\subsubsection{Little Blue}

\paragraph{Environment Perceptions\\\\}

The environment generates the following three kinds of perceptions to \textit{little blue} agent.
 
\begin{itemize}
\item{\texttt{responsable\underline{ }quad (X,Y)}: coordinates of the quadrants inside a crossing that the \textit{little blue} owns.}
\item{\texttt{step(T)}: since our environment class extends \textit{Jason's} \textit{Time Stepped Environment} class, we unify \textit{T} with the result of environment method \textit{getSteps()}. We use the \textit{T} to let the \textit{little blue} control the time to change the directions allowed on an intersection.}
\item{\texttt{street\underline{ }cell(X,Y,Ob)}: for each step, the environment add perceptions of the content of \textit{little blue} crossing cells. \textit{Ob} can be unified with \textit{walker} if there is an agent walking in the coordinate \textit{X, Y}, or \textit{empty} if there is no \textit{walker} at the cell.}
\end{itemize}

\paragraph{Communication with other agents\\\\}

As shown in Figure~\ref{Figure:AgentsCommunication}, there is two moments that a \textit{little blue} agent communicates with a \textit{walker} agent. The first one is when the execution starts and all \textit{little blue} agents send a broadcast message \texttt{coordinator(N)} in which \textit{N} is unified with the agent name. The goal of this first message is to let the \textit{walker} agents know which traffic coordinators exists in the environment. The second moment that a \textit{little blue} communicates with a \textit{walker} is when the \textit{walker} that asked for permission to cross the intersection is allowed to cross. In this case the \textit{little blue} sends a \texttt{can\underline{ }cross(D)} message, where \textit{D} is the direction allowed on the asked quadrant.

\subsection{Environment}
\label{Section:Implementation:Environment}

The \texttt{StreetEnv} class is the abstraction  class for the traffic control environment. The environment class is responsible for updating the agents belief base and answer to agent actions. Its method \textit{updateAgPercept} checks the kind of agent and his \textit{id} to then update the agent beliefs as explained in Section \ref{Section:Implementation:Agents}.

There are two actions that can be executed by agents in the environment. The \textit{walker} agent executes a \texttt{move(Direction)} action, in which the parameter \textit{Direction} can be unified with: up, down, left or right. The environment then checks if there is no obstacles, and if the next position, given the selected direction, is inside the environment grid, to then change the agent position. When the next position is not inside the grid, the \textit{agent} returns to its start position. The \textit{little blue} agent in practice does not change the environment, but instead it \textit{tells} the environment (that is also designed to be a controller to the grid view) which stop positions in the grid are ``green" and which ones are ``red". This action reflects on a better visualization of which agent has the preference to cross each intersection.

\subsection{Model}
\label{Section:Implementation:Model}

The \texttt{StreetModel} class stores all information related to the selected environment. It stores the number of \textit{walkers}, their streets; the traffic coordinators and the quadrants they are responsible for; and the \textit{signal color} of each stop (semaphore). The model is the class responsible to update the grid view after each agent action executed in the environment.

\subsection{View}
\label{Section:Implementation:View}

The Figure~\ref{Figure:GridView} shows the traffic control grid. The obstacles are green diamonds, while the \textit{walker} agents are the red circles moving into gray squares (part of streets). The outlines that exist in some cells that are adjacent to an intersection, represent the stops. The green outline indicates that the \textit{agent} on that stop has the preference for crossing, while the red outline indicates that the \textit{walker} must wait to cross it. 

\begin{figure}[h!]
\centering
\scalebox{0.35}{
	\epsfig{file=images/grid-view}}
\caption{User interface of the traffic-control application with 3 crossings and high traffic intensity.} 
\label{Figure:GridView}
\end{figure}

\section{Conclusion}
\label{Section:Conclusion}

We developed a real-world simulation of a traffic control in situations that a traffic coordinator is called to handle the traffic (normally when there is a problem with semaphores). Our agents get perceptions that make sense to get from the environment, like perceptions of what is around and the direction of the street that he is into. We also explored communication by making all \textit{walker} agents that are close to a intersection, stop and talk with the traffic coordinator to decide if he can cross the intersection.

We think that this project was a great experience to design not only the agents but also the \textit{Jason} environment, model, and view, to get a good overview of a multi-agent system simulation.

For next classes we suggest a division into two deliverables, maybe in an incremental way: like the first deliverable is a version of the system doing \textit{X} features, and the final version should do \textit{X + Y}.

\newpage
\section{Appendix : UML}

\begin{figure}[h!]
\centering
\scalebox{0.3}{
	\epsfig{file=images/uml-java}}
\caption{Traffic Control Java UML.} 
\label{Figure:UML}
\end{figure}


\end{document}
